package bTree.LeetCode;

public class 单词搜索 {
    int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public boolean exist(char[][] board, String word) {
        int row = board.length;
        int line = board[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < line; j++) {
                if (board[i][j] == word.charAt(0)) {
                    boolean[][] visited = new boolean[row][line];
                    boolean success = dfs(board, word, visited, i, j, 1);
                    if (success) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, boolean[][] visited, int row, int line, int cnt) {
        if (cnt==word.length()){
            return true;
        }
        visited[row][line]=true;
        for (int i = 0; i < 4; i++) {
            int newRow = row + dir[i][1];
            int newLine = line + dir[i][0];
            if (newRow<0||newRow>=board.length||newLine<0||newLine>=board[0].length||visited[newRow][newLine]||board[newRow][newLine]!=word.charAt(cnt)){
                continue;
            }
            boolean dfs = dfs(board, word, visited, newRow, newLine, cnt + 1);
            if (dfs){
                return true;
            }
        }
        visited[row][line] = false;
        return false;
    }
}